package com.ting.test.algorithms.滑动窗口;

import java.util.LinkedList;
import java.util.Stack;

/**
 * Created by 雷霆 on 2020/11/6.
 * <p>
 * Description：
 * 给定一个可能含有重复值的数组arr，i位置的数一定存在如下两个信息
 * <p>
 * 1）arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪？
 * <p>
 * 2）arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪？
 * <p>
 * 如果想得到arr中所有位置的两个信息，怎么能让得到信息的过程尽量快。
 */
public class NearMinArr {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
        int[][] result = printMin(arr);
//        for (int res : result) {
//            System.out.println(res);
//        }
    }

    private static int[][] printMin(int[] arr) {
        if (null == arr || arr.length < 1) {
            return null;
        }
        int length = arr.length;
        int index = 0, R = 0;
        int[][] result = new int[length][2];
        //单调栈结构 stack 中维护一个从小到大的单调栈 List用于存储重复的值
        Stack<LinkedList<Integer>> windows = new Stack<>();

        while (R < length) {
            //如果arr[R] 小于arr[windows.last] 则表示出现了最小值
            while (!windows.isEmpty() && arr[R] < arr[windows.peek().getLast()]) {
                LinkedList<Integer> topList = windows.pop();
                for (Integer num : topList) {
                    result[num][0] = windows.isEmpty() ? -1 : windows.peek().getLast();
                    result[num][1] = R;
                }
                break;
            }
            //如果arr[R] == arr[windows.last] 则表示出现了最小值
            if (!windows.isEmpty() && arr[R] == arr[windows.peek().getLast()]) {
                windows.peek().add(R);
                break;
            }
            //否则 即arr[R] 大于arr[windows.last] 直接压栈
            LinkedList linkedList = new LinkedList<Integer>();
            linkedList.addLast(R);
            windows.push(linkedList);
            R++;
        }
        //当数组遍历完成之后，还需要再次判断stack中是否还有值，如果有，则表示还有数据么有弹出，这些数据都是没有相邻的最小值的
        while (!windows.isEmpty()) {
            LinkedList<Integer> topList = windows.pop();
            for (Integer num : topList) {
                result[num][0] = windows.isEmpty() ? -1 : windows.peek().getLast();
                result[num][1] = -1;
            }
            break;
        }
        return result;
    }


}
